class Solution:
    def insert(self, intervals, newInterval):
        if len(intervals) == 0:
            return [newInterval]
        res, insert_index, flag = [], len(intervals), False
        start_num, end_num = min(intervals[-1][0], newInterval[0]), max(intervals[0][1], newInterval[1])
        for index, num in enumerate(intervals):
            if num[1] < newInterval[0] or num[0] > newInterval[1]:
                res.append(num)
            else:
                insert_index = min(index, insert_index)
                start_num = min(num[0], start_num)
                end_num = max(num[1], end_num)
                flag = True
        if flag:
            res.insert(insert_index, [start_num, end_num])
        else:
            res.append(newInterval)
            res.sort()
        return res

"".sp
a = Solution()
# print(a.insert(intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]))
# print(a.insert(intervals = [], newInterval = [4,8]))
print(a.insert(intervals=[[1, 5]], newInterval=[6, 8]))
print(a.insert(intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval=[4, 8]))

